jhcarl0814.github.io Augmented Containers Sequence augmented_*****_t augmented_deque_t Associative augmented_***​/​***​/​********​/​********_t ***** augmented_*****_t
enum class augmented_sequence_physical_representation_e { rb3p, rb2p, finger_tree, }; enum class augmented_sequence_size_management_e { no_size, at_node_end, at_each_node_except_node_end, }; template< typename element_t, typename allocator_t = std::allocator<element_t>, typename accumulator_t_ = augmented_sequence_helpers::empty_accumulator_t, typename augmented_sequence_physical_representation_t = std::integral_constant<augmented_sequence_physical_representation_e, augmented_sequence_physical_representation_e::rb3p>, typename augmented_sequence_size_management_t = std::integral_constant<augmented_sequence_size_management_e, augmented_sequence_size_management_e::at_each_node_except_node_end> > struct augmented_sequence_t;
template< typename element_t, typename allocator_t, typename accumulator_t, typename augmented_sequence_physical_representation_t, typename augmented_sequence_size_management_t > requires(static_cast<augmented_sequence_physical_representation_e>(augmented_sequence_physical_representation_t{}) == augmented_sequence_physical_representation_e::rb2p) struct augmented_sequence_t;
template< typename element_t, typename allocator_t, typename accumulator_t, typename augmented_sequence_physical_representation_t, typename augmented_sequence_size_management_t > requires(static_cast<augmented_sequence_physical_representation_e>(augmented_sequence_physical_representation_t{}) == augmented_sequence_physical_representation_e::rb3p) struct augmented_sequence_t;
augmented_sequence_t is an augmented, general-purpose sequence. It's part of the augmented containers library, providing a stronger version of sequence containers (let containers (and possibly its subranges) always have several accompanying results of algorithms/views), as well as <algorithm> and <ranges> (when the input sequence changes, refresh output values/ranges in logarithmic time complexity).
| members | |||
| iterator::operator++ iterator::operator-- |
split_emit_left split_emit_right |
||
| physical representation |
red-black tree two pointers per node |
O(1) | At the beginning of split operation, spends O(1) time to get predecessor of the element at the split position. In the first round of split operation, spends O(1) time to get insert position in the subtree. |
| red-black tree three pointers per node |
O(lg(N)) (amortized O(1)) | At the beginning of split operation, spends O(lg(N)) time to get predecessor of the element at the split position. In the first round of split operation, spends O(lg(N)) time to get insert position in the subtree. |
|
| members | ||||
| size | iterator | split_emit_left split_emit_right |
||
| size management |
does not store size | not supported | ||
| stores size at end node | At the end of split operation, spends O(distance(rangeemitted)) time to restore the sizes. | |||
| stores subtree sizes at each node except node end | Can get index of iterator and has all functions required by std::random_access_iterator, all take O(lg(N)) time. ⚠iterator::iterator_concept is still std::bidirectional_iterator_tag because of time complexity requirements. |
|||
The untagged pointers are drawn as solid lines. The 0b1-tagged pointers are drawn as dashed lines.
In rb3p's examples, end node's child_right, parent and child_left are drawn separately to not break graphviz's layout.
In rb2p's examples, non-end node's loop (node's my_list_beign() → node's child_right, node's child_right's next() → node's leftmost_descendent_of_child_right, node's leftmost_descendent_of_child_right's my_list_begin() → node's rightmost_descendent_of_child_left, node's rightmost_descendent_of_child_left's my_list_beign() → node's child_left, node's child_left's next() → node, the last edge of the loop is 0b1-tagged) has it's edges drawn end-to-end to make it clearer (the pointers are still pointing to whole nodes, not members of nodes).
In rb2p's examples, end node's loop (end node's my_list_beign() → leftmost_descendent_of_root, leftmost_descendent_of_root's my_list_beign() → root, root's next() → rightmost_descendent_of_root, rightmost_descendent_of_root's my_list_beign() → end_node, the last edge of the loop is 0b1-tagged) is not drawn to not break graphviz's layout.
In rb2p's examples, end node has my_list_beign_, non-end node has my_list_beign_ and next_. The bit210 of my_list_beign_ stores the role of the node (there are 8 roles: end△, root▽, child_left_not_a_leftmost_descendent◤, child_left_leftmost_descendent_of_non_root◢, child_left_leftmost_descendent_of_root◁, child_right_not_a_rightmost_descendent◥, child_right_rightmost_descendent_of_non_root◣, child_right_rightmost_descendent_of_root▷), the other bits are used to store my_list_beign(). The bit2 of next_ stores the color of the node (reflected on the color of cells' borders), the bit1 of next_ stores whether my_list_beign() is 0b1-tagged, the bit0 of next_ stores whether next() is 0b1-tagged, the other bits are used to store next().
The accumulation step is skipped. What's left (when augmented_sequence_size_management_t is augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end) can be seen as a std::vector/std::deque that supports fast split/concatenate and never invalidates iterators/references/pointers, or a std::list with random access ability.
augmented_containers::augmented_sequence_t< char, std::allocator<char>, augmented_containers::augmented_sequence_helpers::empty_accumulator_t, ... > augmented_sequence;
| static_cast​<​augmented_containers​::​augmented_sequence_size_management_e​>​(​augmented_sequence_size_management_t​{​}​) | ||||
| augmented_containers​::​augmented_sequence_size_management_e​::​no_size | augmented_containers​::​augmented_sequence_size_management_e​::​at_node_end | augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end | ||
| static_cast​<​augmented_containers​::​augmented_sequence_physical_representation_e​>​(​augmented_sequence_physical_representation_t​{​}​) | augmented_containers​::​augmented_sequence_physical_representation_e​::​rb2p | |||
| augmented_containers​::​augmented_sequence_physical_representation_e​::​rb3p | ||||
element_t(char)s are accumulated into accumulated_storage_t(std::string)s.
augmented_containers::augmented_sequence_t< char, std::allocator<char>, augmented_containers::augmented_sequence_helpers::accumulator_sequence_t<char, std::string>, ... > augmented_sequence;
| static_cast​<​augmented_containers​::​augmented_sequence_size_management_e​>​(​augmented_sequence_size_management_t​{​}​) | ||||
| augmented_containers​::​augmented_sequence_size_management_e​::​no_size | augmented_containers​::​augmented_sequence_size_management_e​::​at_node_end | augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end | ||
| static_cast​<​augmented_containers​::​augmented_sequence_physical_representation_e​>​(​augmented_sequence_physical_representation_t​{​}​) | augmented_containers​::​augmented_sequence_physical_representation_e​::​rb2p | |||
| augmented_containers​::​augmented_sequence_physical_representation_e​::​rb3p | ||||
element_t(int)s' addresses and arrays thereof are accumulated into their std::ranges::merge | std::views::take(3) (stores addresses so you can modify the original elements).
augmented_containers::augmented_sequence_t< int, std::allocator<int>, augmented_containers::augmented_sequence_helpers::accumulator_wrapping_accumulating_binary_functor_t<accumulating_min_n_element_binary_functor_t<int, 3, true>>, ... > augmented_sequence;
| static_cast​<​augmented_containers​::​augmented_sequence_size_management_e​>​(​augmented_sequence_size_management_t​{​}​) | ||||
| augmented_containers​::​augmented_sequence_size_management_e​::​no_size | augmented_containers​::​augmented_sequence_size_management_e​::​at_node_end | augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end | ||
| static_cast​<​augmented_containers​::​augmented_sequence_physical_representation_e​>​(​augmented_sequence_physical_representation_t​{​}​) | augmented_containers​::​augmented_sequence_physical_representation_e​::​rb2p | |||
| augmented_containers​::​augmented_sequence_physical_representation_e​::​rb3p | ||||
Each element_t(int)'s corresponding accumulated_storage_t comes with the navigator portion (prev and next pointers) to be ready to form a circular doubly linked list. The accumulator takes chunk-begins (std::ranges::prev(it).is_end() || (*std::ranges::prev(it) < 50) != (*it < 50)), discards non-chunk-begins (and takes other accumulated circular doubly linked lists), accumulates them into a circular doubly linked lists representing std::ranges::chunk_by_view of the original sequence.
augmented_containers::augmented_sequence_t< int, std::allocator<int>, diffing_adjacent_element_accumulator_t, ... > augmented_sequence;
| static_cast​<​augmented_containers​::​augmented_sequence_size_management_e​>​(​augmented_sequence_size_management_t​{​}​) | ||||
| augmented_containers​::​augmented_sequence_size_management_e​::​no_size | augmented_containers​::​augmented_sequence_size_management_e​::​at_node_end | augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end | ||
| static_cast​<​augmented_containers​::​augmented_sequence_physical_representation_e​>​(​augmented_sequence_physical_representation_t​{​}​) | augmented_containers​::​augmented_sequence_physical_representation_e​::​rb2p | |||
| augmented_containers​::​augmented_sequence_physical_representation_e​::​rb3p | ||||
Similar to the accumulator_yield_one_view example, except that each accumulated_storage_t has "a map from element % 3 to circular doubly linked list's end node" (instead of just "one end node"). The result represents C++32's std::ranges::group_by_view of the original sequence (navigator_style = std::ranges::group_by_view::navigator_style_t::circular_doubly_linked_list, map_container_tt = std::map).
augmented_containers::augmented_sequence_t< int, std::allocator<int>, group_by_element_accumulator_t, ... > augmented_sequence;
| static_cast​<​augmented_containers​::​augmented_sequence_size_management_e​>​(​augmented_sequence_size_management_t​{​}​) | ||||
| augmented_containers​::​augmented_sequence_size_management_e​::​no_size | augmented_containers​::​augmented_sequence_size_management_e​::​at_node_end | augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end | ||
| static_cast​<​augmented_containers​::​augmented_sequence_physical_representation_e​>​(​augmented_sequence_physical_representation_t​{​}​) | augmented_containers​::​augmented_sequence_physical_representation_e​::​rb2p | |||
| augmented_containers​::​augmented_sequence_physical_representation_e​::​rb3p | ||||
element_t(std::string)s' .size()s are accumulated by std::size_t operator+(std::size_t, std::size_t). Use .find_by_monotonic_predicate([&](){ ... }) to find the first element where the accumulated_storage_t(std::size_t) (accumulated string size so far) starts to be greater than the given character index, i.e., the element that contains the the given character indexth character. Note that the hierarchical structure saves time by skiping substructures that don't contain the results.
augmented_containers::augmented_sequence_t< std::string, std::allocator<std::string>, augmented_containers::augmented_sequence_helpers::accumulator_wrapping_accumulating_binary_functor_t<accumulating_binary_functor_string_length>, ... > augmented_sequence;
| static_cast​<​augmented_containers​::​augmented_sequence_size_management_e​>​(​augmented_sequence_size_management_t​{​}​) | ||||
| augmented_containers​::​augmented_sequence_size_management_e​::​no_size | augmented_containers​::​augmented_sequence_size_management_e​::​at_node_end | augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end | ||
| static_cast​<​augmented_containers​::​augmented_sequence_physical_representation_e​>​(​augmented_sequence_physical_representation_t​{​}​) | augmented_containers​::​augmented_sequence_physical_representation_e​::​rb2p | |||
| augmented_containers​::​augmented_sequence_physical_representation_e​::​rb3p | ||||
element_t(int)s are accumulated into their std::ranges::max. Use .find_by_heap_predicate(jts_output, [&](){ ... }) to eagerly find all elements greater than or equal to the given threshold. Note that the hierarchical structure saves time by skiping substructures that don't contain the results. It's possible to parallelize the search, depending on the availability of std::execution.
augmented_containers::augmented_sequence_t< int, std::allocator<int>, augmented_containers::augmented_sequence_helpers::accumulator_wrapping_accumulating_binary_functor_t<augmented_containers::augmented_sequence_helpers::accumulating_binary_functor_wrapping_homogeneous_binary_functor_t<int, augmented_containers::augmented_sequence_helpers::max_t<int>>>, ... > augmented_sequence;
| static_cast​<​augmented_containers​::​augmented_sequence_size_management_e​>​(​augmented_sequence_size_management_t​{​}​) | ||||
| augmented_containers​::​augmented_sequence_size_management_e​::​no_size | augmented_containers​::​augmented_sequence_size_management_e​::​at_node_end | augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end | ||
| static_cast​<​augmented_containers​::​augmented_sequence_physical_representation_e​>​(​augmented_sequence_physical_representation_t​{​}​) | augmented_containers​::​augmented_sequence_physical_representation_e​::​rb2p | |||
| augmented_containers​::​augmented_sequence_physical_representation_e​::​rb3p | ||||
element_t(int)s are accumulated into their std::ranges::max. Use .find_by_heap_predicate_generator([&](){ ... }) to lazily iterate through elements greater than or equal to the given threshold, until an element divisible by the given denominator is encountered. Note that the hierarchical structure saves time by skiping substructures that don't contain the results. It's possible to parallelize the search, depending on the availability of std::execution.
augmented_containers::augmented_sequence_t< int, std::allocator<int>, augmented_containers::augmented_sequence_helpers::accumulator_wrapping_accumulating_binary_functor_t<augmented_containers::augmented_sequence_helpers::accumulating_binary_functor_wrapping_homogeneous_binary_functor_t<int, augmented_containers::augmented_sequence_helpers::max_t<int>>>, ... > augmented_sequence;
| static_cast​<​augmented_containers​::​augmented_sequence_size_management_e​>​(​augmented_sequence_size_management_t​{​}​) | ||||
| augmented_containers​::​augmented_sequence_size_management_e​::​no_size | augmented_containers​::​augmented_sequence_size_management_e​::​at_node_end | augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end | ||
| static_cast​<​augmented_containers​::​augmented_sequence_physical_representation_e​>​(​augmented_sequence_physical_representation_t​{​}​) | augmented_containers​::​augmented_sequence_physical_representation_e​::​rb2p | |||
| augmented_containers​::​augmented_sequence_physical_representation_e​::​rb3p | ||||